tablestg 0.1.0

// Main structure is IndexedFile ( similar to  Vec )
// An indexed file has records with fields.
// A field can be fixed size or variable size
// Records are stored in pages
// Each record has an Id
// Large field values are stored as an Indexed file with chunks, with the trailing bytes stored inline.
// A page of an indexed file can be a single page-store page, or several ( but not more than 64KB in total ).
// Example record:
// Cust ( email string(64), name string(64) ... )
// The maximum inline size here is 128 bytes, so we could store up to 500 records per page.
// However, we want a smaller page size, so store say 50 records per page.

/*
Suppose we have Cust file

1 'george.barwood@gmail.com' 'George Barwood'
2 'marilyn.barwood@gmail.com' 'Marilyn Barwood'

This could be stored in a 2kb page as 4 16 byte offsets, with the byte data stored at the end of the page.
The PageType is Simple.

Special files
The Chunk special files are used to store oversize strings and small pages.
For example a string of length 1030 could be stored as 4 chunks of 255 bytes, with 10 bytes left over (stored inline).
The storage spec is chunk file id, starting id, number of chunks, left-over bytes. 
A Chunk file has fixed size records.

Page density
============
If a page becomes sparse, that is it has many deleted records, it is stored in Hash format using ph (perfect hash) crate.
There are N (typically 256) hash slots. A hash slot consists of the record id (one byte) and record data.
We lookup by computing a hash of the id, and check that position.
*/

/*

// Page flags
enum PageType {
    Simple,    // Page is simple Vec of fixed size records.
    Hashed,    // Page is hash table followed by fixed size records.
    Var,       // Page is simple Vec of offsets to variable size records.
    VarHashed, // Page is hash table of offsets to variable size records.
}

struct PageInfo {
    typ: PageType,
    leaf: bool,
    deletions: VecId,
}

type VecId = u64;
*/

/* Non-hashed page layout...
   List of offsets (0 indicates a deleted element)
   < Free Space >
   Record Data
*/

struct IndexedFile<'a>
{
    apd: &'a AccessPagedData,
    root: u64,
    recs_per_page: u16,
    record_count: u64,
}

struct PageInfo
{
    recsize : u16,    // 0 indicates records are variable size
    used : u16,       // Bytes allocated for page data
}

use page_store::AccessPagedData;

impl <'a> IndexedFile<'a> {
    fn new(apd: &'a AccessPagedData, root: u64) -> Self {
        Self {apd, root, recs_per_page: 256, record_count: 0}
    }

    /// Call function f for each record in specified range with data reference.
    fn foreach<F>(_f: F, _start: u64, _count: u64)
    where
        F: FnMut(u64, &DataRef) -> bool,
    {
        todo!()
    }

    fn insert( _id: u64, _data: &[u8] )
    {
        // Get the page to be written
        // Deallocate existing data ( unless it is the same size as existing data )
        // Allocate space for new data
        // Copy data into allocated space ( encode data length if records are not fixed size )
        // Assign the offset in the page to point to the data
        let _page_index = id % 256;
        todo!()
    }


    /// Get page number at index ix at specified level.
    fn get_page_num(&self, mut pnum: u64, level: u8, mut ix: u64) -> u64 {
        if level > 1 {
            let x = ix / self.base;
            ix %= self.base;
            pnum = self.get_page_num(blk, level - 1, x);
        }
        self.get_num(pnum, ix)
    }

    /// Get page number from specified page at specified index
    fn get_num(&self, pnum: u64) -> u64
    {
        todo!()
    }
}

struct DataRef<'a> {
    page: &'a [u8],
    off: usize,
}

fn main() {
    println!("Hello World");

    use ph::fmph;

    let keys = [1, 2, 3, 8, 9, 10, 20, 22, 24];
    let f = fmph::Function::from(keys.as_ref());
    // f assigns each key a unique number from the set {0, 1, 2}
    for k in keys { println!("The key {} is assigned the value {}.", k, f.get(&k).unwrap()); }

    println!("f bytes={}", f.write_bytes());

    for i in 1..=30 { println!("f.get({})={:?}", i, f.get(&i)); }
}


/// Implementation of large persistent vector.
///
/// The vector is constructed from a tree of pages.
/// The leaf-level (data) pages have user-data, the branch-level blocks
/// have lists of page numbers ( base is number of pages numbers per branch page ).
///
/// Diagram for 3-level tree ( extra levels = 2 ), base = 3, 5 records..
///
///   Level 0 : Root Page (2 entries)
///
///   Level 1 : Branch 0 (3 entries)         Branch 1 (2 entries)      
///
///   Level 2 : Rec 0 | Rec 1 | Rec 2     Rec 3 | Rec 4

struct PerVec
{
    base: u64,
    apd: &'a AccessPagedData,
    root: u64,
    levels : u8,
}

impl PerVec
{
    /// Get the page number at index ix at specified level. Returns zero if page does not exist.
    fn get_page(&self, mut page: u64, level: u8, mut ix: u64) -> u64 {
        if level > 1 {
            let x = ix / self.base;
            ix %= self.base;
            page = self.get_page(page, level - 1, x);
        }
        self.get_num(page, ix)
    }

   ./// Get a page number from a page
   fn get_num(&self, page: u64, ix:u64) -> u64
   {
       if page == 0 { return 0; }
       let data = apd.get_data(page);
       let off = ( ix as usize ) * 8;
       if off + 8 <= data.len()
       {
           let data = &data[off..off + 8];
           Some( u64::from_le_bytes(data.try_into().unwrap()) )
       }
       else { 0 }
   }

   /// Get page number associated with specified index. Returns zero if page does not exist.
   fn get_data_page(&self, ix: u64) -> u64
   {
       if self.levels == 0 { return self.root; }
       self.get_page( self.root, self.levels, ix ) 
   }
}